package com.zzz.offer.ischildtree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class IsChildTree {

    Stack<TreeNode> stackMater = new Stack<>();
    Stack<TreeNode> stackChild = new Stack<>();
    List<TreeNode> tree = new ArrayList<>();

    // 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {

        // 用最原始的 方法 能想得到的方法
        // 数的子结构就 和 字符串子串匹配 类似
        // 遍历主串，拿子串第一个字符匹配，遇到 第一个相同的字符
        // 然后接着拿子串第二个字符和主串后续一个字符匹配
        // 如果匹配成功，那么接着拿第三个继续匹配
        // 如果匹配失败，那么主串回到之前第一个相同的字符串位置
        // 开始拿下一个字符与子串第一个字符比较。。。回到最初的阶段
        // 知道匹配成功子串最后一个字符，就完成匹配任务，说明是一个子串

        // 那么从上面的简单逻辑上，没有KMP算法思想，没有状态机加层，我们就用最简单的思想完成子树判断

        // 字符串的遍历因为就相当于单链表，所以直接往后取就行
        // 但是二叉树的遍历因为存在树结构，所以必须要以树的遍历来进行匹配元素

        // 树的遍历又涉及到子结点，因为如果是一个树的子树，这个子树很有可能在树的任意位置
        // 子树从树中剥离开来，那么它的子结点可以为空，但树上就不一定
        // 所以为了保持和子树原来一样的顺序遍历匹配， 使用了栈来存储匹配中的元素
        // 根据相同结点，将对应结点放入栈中，然后拿到下一个不匹配，那么就回退到树的下一个元素
        // 直到栈中的元素从放进去到出栈为空，那么说明就是一棵子树

        // 如果根节点都是空的那还用比较？
        if (root1 == null || root2 == null) {
            return false;
        }

        listNode(root1);
        for (TreeNode treeNode : tree) {
            if (checkIsChildTree(treeNode, root2, true)) {
                return true;
            }
        }

        return false;
    }

    // 树的所有节点放进List中
    public void listNode(TreeNode node) {
        if (node == null) {
            return;
        }
        tree.add(node);

        listNode(node.left);
        listNode(node.right);
    }

    // 参数 isRoot 表示当前比较是否是 treeB的根节点，
    public boolean checkIsChildTree(TreeNode treeA, TreeNode treeB, boolean isRoot) {

        // 如果treeB节点为空 那直接返回true  treeB的孩子节点为空不需要进行比较
        if (treeB == null) {
            return true;
        }

        // 比较规则
        // treeB 不为空，那么就必须要求 treeA不为空且必须 值相同 相同返回true，不同返回false
        // 若treeB节点为空那么 就相当于成功，返回true

        // 1.比较当前结点  如果返回false 直接返回 如果返回true，接着比较左孩子节点
        if (treeA == null || treeA.val != treeB.val) {
            return false;
        }

        // 如果是根节点，那必须先清空上一次匹配生成的stack
        if (isRoot) {
            stackMater.clear();
            stackChild.clear();
        }

        // 该节点匹配成功，就将节点加入 stack 中
        stackMater.push(treeA);
        stackChild.push(treeB);


        // 2.比较左孩子   如果返回false 直接返回 如果返回true，接着比较右孩子节点
        if (!checkIsChildTree(treeA.left, treeB.left, false)) {
            return false;
        }

        // 3.比较右孩子   如果返回false 直接返回 如果返回true 就相当于本节点包括子树都匹配成功，将栈中当前节点 移除
        if (!checkIsChildTree(treeA.right, treeB.right, false)) {
            return false;
        }

        stackMater.pop();
        stackChild.pop();

        // 4.判断当前是否是根节点层，如果是判断Stack 是否 是空，
        // 如果是空表示 匹配子树成功，否则 当前节点未匹配到，
        //  ---------------------------------------------
        // 想了想，若是出现匹配异常就直接返回false了，不需要判断stack是否为空
        return true;
    }
}

